package leetcode.offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName T07
 * @Description TODO
 * @Author Fanxc
 * @DATE 2020/11/29 0029 21:35
 * @Version 1.0
 */
public class T07 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
   }

    class Solution {
        /**
         * @Author Fanxc
         * @Description //TODO
         * @Date 2020/11/29 0029 21:54
         * @Param [preorder, inorder]
         * @return leetcode.offer.T07.TreeNode
         **/

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder == null || preorder.length == 0) {
                return null;
            }
            int length = preorder.length;
            Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>(length);
            for (int i = 0; i < length; i++) {
                indexMap.put(inorder[i], i);
            }
            TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
            return root;
        }
        /**
         * @Author Fanxc
         * @Description //TODO
         * @Date 2020/11/29 0029 21:54
         * @Param [preorder, preorderStart, preorderEnd, inorder, inorderStart, inorderEnd, indexMap]
         * @return leetcode.offer.T07.TreeNode
         **/

        public TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
            if (preorderStart > preorderEnd) {
                return null;
            }
            int rootVal = preorder[preorderStart];
            TreeNode root = new TreeNode(rootVal);
            if (preorderStart == preorderEnd) {
                return root;
            } else {
                int rootIndex = indexMap.get(rootVal);
                int leftNodes = rootIndex - inorderStart, rightNodes = inorderEnd - rootIndex;//左右结点的个数
                TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes, inorder, inorderStart, rootIndex - 1, indexMap);
                TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
                root.left = leftSubtree;
                root.right = rightSubtree;
                return root;
            }
        }
    }
}
